class Solution {
    List<List<Integer>> ans = new ArrayList<>();

    public void dfs(int c, int n, boolean[] flags, int[] temp, int[] nums) {
        if(c == n) {
            ArrayList<Integer> t = new ArrayList<>();
			for (int i = 0; i < temp.length; i++) {
				t.add(temp[i]);
			}
			ans.add(t);
			return;
        }

        for(int i = 0; i < n; i++) { //按顺序选
			if(!flags[i]) {	//表示当前位置没有被选取
                temp[c] = nums[i];
				flags[i] = true;
				dfs(c + 1, n, flags, temp, nums);
				flags[i] = false;
			}
		}
    }

    public List<List<Integer>> permute(int[] nums) {
        // if(nums.length == 1) {
        //     ArrayList<Integer> temp = new ArrayList<>();
        //     temp.add(nums[0]);
        //     ans.add(temp);
        //     return ans;
        // }

        int n = nums.length;
        boolean[] flags = new boolean[n];
        int[] temp = new int[n];
        dfs(0, n, flags, temp, nums);
        return ans;
    }
}